import java.io.File;
import java.util.LinkedList;
import java.util.Queue;

/**
 */
public class MyBFS {

    private Digraph G;
    private Queue<Integer> queue;

    private int numVertices;
    private int[] edgeTo;
    private int[] distTo;
    private boolean[] marked;

    public MyBFS(Digraph G) {
        this.G = G;
        System.out.println(G.toString());
        numVertices = G.V();

        edgeTo = new int[numVertices];
        distTo = new int[numVertices];
        marked = new boolean[numVertices];

        queue = new LinkedList<Integer>();
        int startAt = 11;
        queue.add(startAt);       //start at root for now
        edgeTo[startAt] = -1;

        while (!queue.isEmpty()) {
            int v = queue.remove();
            marked[v] = true;
            for (Integer i : G.adj(v)) {
                if (!marked[i]) {
                    queue.add(i);
                    distTo[i] = distTo[v] + 1;
                    edgeTo[i] = v;
                }
            }
        }
    }

    public String toString() {
        StringBuffer sb = new StringBuffer();
        sb.append(String.format("%10s %10s %10s %10s", "v", "edgeTo","distTo", "marked\n"));
        for (int v=0;v<numVertices;v++) {
            sb.append(String.format("%10s %10s %10s %10s", v, edgeTo[v],distTo[v], marked[v]+"\n"));
        }

        return sb.toString();
    }


    public static void main(String[] args) {

        try {
            Digraph G = new Digraph(new In(new File("C:\\devel\\src\\main\\data\\digraph1.txt")));
            MyBFS sap = new MyBFS(G);
            System.out.println(sap.toString());
        }
        catch (Exception e) {
            e.printStackTrace();
        }

    }


}
